package com.dylan.历史.算法.排序;

import com.dylan.历史.util.LogUtil;

import java.util.Arrays;

/**
 * Created by Dylan on 2018/10/23.
 */
public class 基础_排序_基数排序 {

    public static void main(String[] args) {
        LogUtil.info(Arrays.toString(radixSort(new int[]{13, 36, 22, 17, 32, 346, 8, 30}, 3)));
    }

    static int[] radixSort(int[] arr, int degree) {
        radixSort(arr, 10, degree);
        return arr;
    }

    /**
     * 基数排序算法 O(logRB)
     * @param arr 待排序数组
     * @param radix 基数（一般是10）
     * @param degree 排序元素的位数,
     *      算法：for(degree=0, x=最大值; x%radix>0 || x/radix>0; x = x / radix) degree++;
     *      例：3位数1；10位数2；123位数3
     */
    static void radixSort(int[] arr, int radix, int degree) {
        int len = arr.length;
        int[] temp = new int[len]; // 用于复制原始数组
        int[] count = new int[radix]; // 用于存储每个余数的元素个数
        int divide = 1; // 用于计算指定位的数值
        for (int i = 0; i < degree; i++) {
            // 拷贝元素
            System.arraycopy(arr, 0, temp, 0, len);
            // 初始化为0
            for (int k = 0; k < count.length; k++) {
                count[k] = 0;
            }
            // 计算各个余数的元素数量
            for (int j = 0; j < len; j++) {
                int remainder = temp[j] / divide % radix; // 数值某个位的余数
                count[remainder]++;
            }
            // 将元素个数累加,count[k]即为余数小于等于k的元素总个数
            for (int k = 1; k < count.length; k++) {
                count[k] = count[k] + count[k - 1];
            }
            // 按余数进行排序
            for (int j = len - 1; j >= 0; j--) {
                int remainder = temp[j] / divide % radix; // 数值某个位的余数
                count[remainder]--; // 此余数的元素个数减1，计算了当前元素需要放置的位置
                arr[count[remainder]] = temp[j]; // 元素放置指定位置
            }
            divide = divide * radix; // 提高一位
        }
    }
}
